package algorithm.leetcode;

public class Num160 {
    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode headA_1 = new ListNode(1);

        ListNode headB = new ListNode(5);
        ListNode headB_1 = new ListNode(6);
        ListNode headB_2 = new ListNode(1);

        ListNode public_1 = new ListNode(8);
        ListNode public_2 = new ListNode(4);
        ListNode public_3 = new ListNode(5);
        public_1.next = public_2;
        public_2.next = public_3;

        headA.next = headA_1;
        headA_1.next = public_1;

        headB.next = headB_1;
        headB_1.next = headB_2;
        headB_2.next = public_1;

        System.out.println(headA);
        System.out.println(headB);
        ListNode intersectionNode = getIntersectionNode(headA, headB);
        System.out.println(intersectionNode);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
